﻿// 同在一直线上的点.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
	int maxPoints(vector<vector<int>>& points) 
	{
	int len = points.size();
	// 点的数量不够
	if (len < 3)
	{
		return len;
	}
	//解题思路
	//遍历任意两个点，然后比较与其他点的斜率是否相同，
	//找到最大值即可，这样操作下来时间复杂度为O(n^3)，
	//使用hashtable 保存斜率，找出数量最多
	int max_vote = 2;
	for (int i=0;i<len;i++)
	{
		//每个点对应的斜率hash表
		std::unordered_map<double, int> gradient_map;//<k:斜率，v:计数>
		for (int j=0;j<len;j++)
		{
			if (i!=j)
			{
				double dx = points[i][0] - points[j][0];
				double dy = points[i][1] - points[j][1];
				double gradient = dy / dx;
				if (gradient_map.count(gradient))
				{
					gradient_map[gradient]++;//斜率计数器加一加一，[]通过key值来访问value
				}
				else
				{
					gradient_map[gradient] = 2;
				}
				max_vote = std::max(max_vote, gradient_map[gradient]);//每轮选出最大值
			}
		}
	}
	return max_vote;
	}
};
int main()
{
    std::cout << "Hello World!\n";
}


